public class Solution695 {

    int max=0;
    int cur=0;
    int[] dx=new int[]{1,0,-1,0};
    int[] dy=new int[]{0,1,0,-1};

    public int maxAreaOfIsland(int[][] grid) {
        int n=grid.length,m=grid[0].length;
        boolean[][] visit=new boolean[n][m];
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if (grid[i][j]==1 && !visit[i][j]){
                    cur=1;
                    dfs(i,j,n,m,visit,grid);
                    max=Math.max(max,cur);
                }
            }
        }
        return max;
    }

    private void dfs(int x, int y, int n, int m, boolean[][] visit, int[][] grid) {
        max=Math.max(max,cur);
        visit[x][y]=true;
        for (int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if (xx>=0 && xx<n && yy>=0 && yy<m && !visit[xx][yy] && grid[xx][yy]==1){
                cur++;
                dfs(xx,yy,n,m,visit,grid);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution695().maxAreaOfIsland(new int[][]{{0,0,1,0,0,0,0,1,0,0,0,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},
                {0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,0,0,0,0,0,0,1,1,0,0,0,0}}));
    }
}
